1. Field of the Invention
This invention relates to the timing of events in a context that involves an expiration period. In particular the invention relates to resolving wraparound of a counter used for timing and expiration.
2. Related Art
In the last few decades communications systems have been shifting from analog circuit-switched networks to digital packet-switched networks. In addition to the development of protocols for communication over infrastructure that was originally built for analog communications, new protocols are being developed in conjunction with infrastructure that is designed for digital communications.
For communication in a circuit switched network, a physical path is established in order to provide communication between two endpoints. The circuit is maintained for the duration of the communication session, and all information traverses the same circuit path.
In contrast, in a packet-switched network, the information being transmitted between two endpoints is encapsulated as one or more packets, each containing an address. The packet address enables the packet to find its destination when placed on a network having many possible paths and destinations.
A network is generally a collection of segments connected by devices that control the flow of packets between segments (e.g., routers and switches). Since a single block or stream of data may be broken up and transmitted as packets along different paths, there is a chance that some packets will experience delays.
Depending upon the nature of the data being sent and the protocol being used, a delay may result in a request for retransmission. For example, a destination application that fails to receive a packet containing part of a text document may request a retransmission of a packet that failed to arrive after a period of time. For real-time data streams such as video or voice, a delayed packet may become useless. In either case, a delayed packet loses its value to the application and it is desirable to remove it from the network. An example of a protocol that provide for packet timeout is Transmission Control Protocol (TCP).
Switches in a network may remove packets from the network by monitoring the delay associated with the transit of the packet through the switch. This is typically done by associating a timestamp with the packet upon its arrival so that its storage time in the switch can be calculated at the time it is ready to be transmitted. The storage time can then be compared to the allowable delay in the switch to determine whether the packet should be transmitted or discarded (timed out).
A general purpose method of timekeeping that is used in switches and other digital electronic devices and processing systems is to periodically increment a binary register or counter. A counter with a length N will be able to store 2N unique values and will be able to measure a maximum interval of 2N−1. For example, a 5-bit counter starting at 00000 and incremented every 1/16 of a second would reach 11111 at 1 15/16 second, and rollover or wraparound to 00000 at 2 seconds.
Wraparound or rollover is a source of ambiguity for any finite length counter. The length of a period of time that has passed between two observed values of a finite counter cannot be determined just by subtracting the first observed value from the second observed value, since wraparound may or may not have occurred between the two observations. If the result of subtracting the first value from the second value is a negative number, then further operations are required.
For example, following the above example of a 5-bit counter, a packet with a time stamp of 11000 ( 24/16 seconds) compared at a time of 11100 ( 28/16 seconds) and having an allowable expiration time of 1 second would be eligible for transmission if wraparound has not occurred (elapsed time= 4/16 seconds), but may or may not be discarded if wraparound had occurred. Thus, unambiguous timeout calculations typically involve additional computational overhead for accounting of the wraparound of the counter.
Although the computation associated with timekeeping and wraparound accounting for a single packet may not be large in absolute terms, it can be a significant part of the overall effort in handling a packet, given that a router or switch handles millions of packets per second. This also applies to other types of devices that use a finite length counter to examine a timestamp to determine whether a timeout condition exists. Although prior art methods have addressed the problem of wraparound, the commonly used brute-force methods do incur significant overhead.